#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int son[N][2];
int val[N];
int pcnt;
pair<int, int> insert(int x, int y) {
    if (!x) {
        return make_pair(y, 0);
    }
    pair<int, int> res;
    if (val[x] > val[y]) {
        res = insert(son[x][0], y);
        son[x][0] = res.first;
    } else {
        res = insert(son[x][1], y);
        son[x][1] = res.first;
    }
    return make_pair(x, res.second + 1);
}
void solve() {
    pcnt = 0;
    int a, b, m;
    cin >> a >> b >> m;
    long long n;
    cin >> n;
    int rot = 0;
    for (int i = 1; i < n; i++) {
        int now = ++pcnt;
        val[now] = (a + 1ll * i % m * b % m) % m;
        son[now][0] = son[now][1] = 0;
        rot = insert(rot, now).first;
    }
    int now = ++pcnt;
    val[now] = (a + 1ll * n % m * b % m) % m;
    cout << insert(rot, now).second << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("fuwafuwa.in", "r", stdin);
    freopen("fuwafuwa.out", "w", stdout);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}